package com.hqq.exercise.tree;

/**
 * JudgeBalanceTree 判断平衡二叉树
 * 题目描述:
 * 输入一棵二叉树的根结点，判断该树是不是平衡二叉树。
 * 如果某二叉树中任意结点的左右子树的深度相差不超过1，那么他就是一棵平衡二叉树
 * 思路:
 * 后序遍历 遍历某节点的时候已经遍历了它的左右节点 根据左右节点的深度可以判断是否满足平衡二叉树的要求 并且求到当前节点的深度
 * Created by heqianqian on 2017/8/22.
 */
public class JudgeBalanceTree {

    private static TreeNode root;

    static {
        root = new TreeNode(5);
        TreeNode lChild = new TreeNode(10);
        lChild.left = new TreeNode(11);
        lChild.right = new TreeNode(9);

        TreeNode rChild = new TreeNode(70);
        lChild.left = new TreeNode(100);
        lChild.right = new TreeNode(50);

        root.left = lChild;
        root.right = rChild;
    }

    public static void main(String[] args) {
        boolean result = isBalanceTree(root);
        System.out.println(result);
    }

    public static boolean isBalanceTree(TreeNode root) {
        int depth = 0;
        return isBalanced(root, depth);
    }

    public static boolean isBalanced(TreeNode root, int depth) {
        if (root == null) {
            depth = 0;
            return true;
        }
        int left = 0, right = 0;
        if (isBalanced(root.left, left) && isBalanced(root.right, right)) {
            if (Math.abs(left - right) <= 1) {//zz 不是指针depth的值并不会改变啊
                /*求父节点的深度*/
                depth = 1 + ((left > right) ? left : right);
                return true;
            }
        }
        return false;
    }


}
